package twobranchTree.isvalidbst;

import java.util.Stack;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/03/08
 * @author 王光浩
 * @Thinking 使用递归方式进行，方法与one类似，但是没有使用额外的空间来保存中序遍历的结果
 */
public class MyMethodTwo {
	/**
	 * @ 整体思路如下：首先我们需要明确一点，如果一颗二叉树是二叉搜索树，则该树的中序遍历结果一定是升序的。
	 * @ 所有在这个方法中，使用inorder来保存上一个节点的值，然后进行中序遍历，将当前节点的值与inorder值进行
	 * @ 比较，如果inorder大于等于当前节点值，则表明该二叉树的中序遍历结果不是升序的，所以不是二叉搜索树。在
	 * @ 该方法中最喜欢的一点就是：使用一个栈，就完成了二叉树的中序遍历。（nb）
	 * @param root
	 * @return
	 */
	public boolean isValidBST(TreeNode root) {
		Stack<TreeNode> stack=new Stack<TreeNode>();
		double inorder=-Double.MAX_VALUE;
		while(!stack.isEmpty() || root!=null) {
			//将左中节点依次入栈
			while(root!=null) {
				stack.push(root);
				root=root.left;
			}
			root=stack.pop();
			//在中序遍历时结果为升序，前一个节点的value一定比当前节点的value小
			if(inorder>=root.val)return false; 
			inorder=root.val;
			root=root.right;
			
		}
		return true;
	}
}
